#include <stdio.h>
#define MAX_TREE_SIZE 100
//利用数组队列 构建 segment_tree
void build_segment_tree(int arr[],int tree[],int node,int start,int end)
{
    if(start == end)
    {
        tree[node] = arr[start];
        return ;
    }
    int left_node = 2*node + 1;
    int right_node = 2*node + 2;
    int mid = (start + end)/2;
    build_segment_tree(arr,tree,left_node,start,mid);
    build_segment_tree(arr,tree,right_node,mid+1,end);
    tree[node] = tree[left_node] + tree[right_node];
}
void update_segment_tree(int arr[],int tree[],int node,int start,int end,int idx,int value)
{
    if(start == end)
    {
        arr[idx] = value;
        tree[node] = value;
        return ;
    }
    int left_node = 2*node + 1;
    int right_node = 2*node + 2;
    int mid = (start + end)/2;
    if(idx <= mid)
    {
        update_segment_tree(arr,tree,left_node,start,mid,idx,value);
    }
    else
    {
        update_segment_tree(arr,tree,right_node,mid+1,end,idx,value);
    }
    tree[node] = tree[left_node] + tree[right_node];

}

int query_segment_tree(int tree[],int node, int start,int end,int range_l,int range_r)
{
    if(start==range_l && end == range_r)
        return  tree[node];
    
    int left_node = 2*node + 1;
    int right_node = 2*node + 2;
    int mid = (start + end)/2;
    if(mid<range_l)
    {
        return query_segment_tree(tree,right_node,mid+1,end,range_l,range_r);
    }
    else if(range_r <= mid)
    {
        return query_segment_tree(tree,left_node,start,mid,range_l,range_r);
    }
    else
    {
        return query_segment_tree(tree,left_node,start,mid,range_l,mid) +
               query_segment_tree(tree,right_node,mid+1,end,mid+1,range_r); 
    }
}
int main()
{
    int arr[] = {1,3,5,7,9,11};
    int tree[MAX_TREE_SIZE] = {0};
    int arr_size = 6; 
    build_segment_tree(arr,tree,0,0,arr_size-1);
    for(int i=0;i<15;i++)
    {
        printf("tree[%d] = %d \n",i,tree[i]);
    }

    update_segment_tree(arr,tree,0,0,arr_size-1,0,0);
    for(int i=0;i<15;i++)
    {
        printf("tree[%d] = %d \n",i,tree[i]);
    }

    printf("query(%d,%d) = %d \n",1,1, query_segment_tree(tree,0,0,arr_size-1,1,1));
    return 0;
}